This invention relates to error recovery, and more particularly to multi-bit error recovery for gray-code-encoded bit streams.
Electronic systems often use binary codes to represent values. However, binary sequences can have adjacent values that have more than one bit that changes. For example, when incrementing from binary 0111, the next binary value is 1000. All four bits change at about the same time. This can result in errors in a receiver.
Gray codes are often used to avoid the multi-bit changes that occur in binary codes. The number of bits that change in adjacent gray-code values (the hamming distance) is one. For example, the next value after gray-code 0111 is 1111. Only one bit changes at a time, reducing the likelihood of errors during transmission.
In some applications using gray code, the value can jump by more than one. FIGS. 1A–B show a gray-code application with multiple bits changing between samples. In FIG. 1A, transmitter 70 outputs a gray-code sequence onto a communication line to receiver 72. The gray-code value may be converted to serial data and encoded in a variety of ways on the physical communication line, but at some layer in transmitter 70 and in receiver 72 the data is represented as a parallel data word in a gray code sequence.
Different clock domains are used by transmitter 70 and by receiver 72. Transmitter 70 operates with a clock that is 5 times faster than the receive clock, and can be asynchronous. Gray-coded values are advanced in transmitter 70 five times faster than the received values are sampled by receiver 72. Also, transmitter 70 can advance by 2 rather than just by 1 value in the gray-code sequence.
FIG. 1B shows gray-code values transmitted and received with an error. Transmitter 70 is allowed to change more than one bit in the gray code at a time. In general, N bits of the L-bit gray-coded value can change per transmission, so the value can change by 2N−1 per transmission. A standard increment-only gray code has N=1, but in this example N=2. The sequence of values for a 4-bit (L=4) gray code is shown on the left column. This is a reflected gray code, since the lower 2 bits in each group of 4 values are reflected between the adjacent groups of four values.
Both the transmitter and receiver start out with a gray-code value of 0000. The transmitter advances its output value by 2 for several transmit clocks, outputting 0000, then 0011 on the next transmitter clock, then 0110, then 0101, then 1100, and finally 1111, as shown in the second column. This occurs over 5 periods of the transmitter's clock.
The clock for receiver 72 is 5 times slower than the clock for transmitter 70. After the initial value of 0000 is sampled by receiver 72, the next input value is not sampled until 5 transmitter clocks later, when the transmitted value has advanced to 1111. The transmitter changes its output from 1100 to 1111 at about the time the receiver samples the communications line. Since the lower 2 bits are changing during the sampling time, the value sampled by the receiver is 11XX, as the exact value of the lower 2 bits depends on the exact relative timing to the receiver's sample-clock edge.
The value sampled by the receiver, 11XX, could be 1100 is sampled early, or 1111 if sampled late, or 1101 or 1110 is sampled as the 2 lower bits are changing. Metastability could occur in the lower bits, making the value sampled variable. If the receiver samples 1100, 1110, or 1111, the sequencing logic on receiver 72 can probably later receiver, since these gray-code values are less that or equal to the transmitted value of 1111.
However, if receiver 72 samples 1110, a fatal error can occur in logic in receiver 72. The value 1110 is after the transmitted value 1111 in the gray-code sequence. If the gray-code value is a pointer to a memory location in receiver 72, the wrong memory location would be accessed and unknown data could be read.
A handshake signal could be passed between transmitter 70 and receiver 72 to ensure stable data before sampling, but this can add delays and reduce performance. Other examples and applications may have similar problems.
What is desired is a receiver that corrects errors in a received gray-code sequence. An error-corrector for gray-code values that have multiple bits changing at a time is desirable. An error corrector that converges over time to the correct value is desired.